/*
	divide
*/

//全排列
void prem(int *A, int f, int r)
{
	if(f==r)
	{
		for(int i = 0;i<r;i++)
		{
			printf("%d\n", A[i]);
		}
	}
	else
	{
		for(int i = f;i<=r;i++)
		{	
			swap(A[i],A[f]);
			prem(A,f+1,r);
			swap(A[i],A[f]);
		}	
	}
	
}

//组合数
int B[10];
int A[]={1,2,3,4,5};
void combination(int i,int j,int k)
 {
	 int t;
	if(k==0){for(t=0;t<j;t++) printf("%d ",B[t]);printf("\n");return;}
	if(i-k+1>=0)
	{
		B[j++]=A[i];
		combination(i-1,j,k-1);//包含A[i],从剩下的找k-1个数
		combination(i-1,j-1,k);//不包含A[i]，从剩下找k个数
	}
 }

 /*
	整数划分问题

	递归式
	q(n,m):将最大加数不大于m
	
	m=1||n=1
	q(n,m) = 1;

	m>n
	q(n,m) = q(n,n)

	n=m
	q(n,m) = q(n,n-1) + 1

	n>m>1
	q(n,m) = q(n,m-1)+q(n-m,m)
 */

/*
	集合划分问题
	{1}，{2}，{3}，{4}}， {{1，2}，{3}，{4}}， 
	{{1，3}，{2}，{4}}， {{1，4}，{2}，{3}}， 
	{{2，3}，{1}，{4}}， {{2，4}，{1}，{3}}， 
	{{3，4}，{1}，{2}}， {{1，2}，{3，4}}， 
	{{1，3}，{2，4}}， {{1，4}，{2，3}}， 
	{{1，2，3}，{4}}， {{1，2，4}，{3}}， 
	{{1，3，4}，{2}}， {{2，3，4}，{1}}， 
	{{1，2，3，4}} 

	递归式
	q(n,m)表示将n个元素的集合划分成m个子集合构成的集合个数

	m=1
	q(n,m) = 1

	n=m
	q(n,m) = 1

	如果不是以上两种情况
	向n-1个元素划分成的m个集合里面添加一个新的元素，
	另一类是f(n-1, m-1)，然后第n个独立为一份
	则有
	q(n,m) = m*f(n-1,m) + f(n-1,m-1)

*/

 //整数因子划分统计个数
 int total = 0;
 void solve(int n)
 {
 	if(n==1)
 		total++;
 	else
 	{
 		for(int i = 2;i<=n;i++)
 		{
 			if(n%i==0)
 				solve(n/i);
 		}
 	}
 }


/*
	主定理
	f(n) = af(n/b) + d(n)
	1,当d(n)是常数时
		a != 1
		f(n) = O(n^log_b_a) 
		a = 1
		f(n) = O(logn)
	2,当d(n) = cn
		a < b
		f(n) = O(n)
		a = b
		f(n) = O(nlogn)
		a>b
		f(n) = O(n^log_b_a)
*/

/*
	大整数乘法
	X*Y 都是n位
	X = A^ +B
	Y = C^ +D
	XY = (A^ + B)(C^ + D)
	T(n) = O(1) n = 1
	     = 4T(n/2)+O(n)
	T(n) = O(n^2)

	XY = AC^ + ((A-B)(D-C) + AC+BD)^ + BD
	T(n) = 3T(n/2) + O(n)
	T(n) = O(n^log_2_3)
*/

/*
	线性时间选择
	设所有元素互不相同。
	在这种情况下，找出的基准x至少比3(n-5)/10个元素大，
	因为在每一组中有2个元素小于本组的中位数，
	而n/5个中位数中又有(n-5)/10个小于基准x。
	同理，基准x也至少比3(n-5)/10个元素小。
	而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。

	T(n) = T(n/5) + T(3n/4) + Cn
*/
 int select(int *A, int p, int r, int k)
{
	if (r - p < 75)
	{
		bubble(A, p, r);
		return A[p+k-1];
	}

	int group = (r-p+5)/5;//组数

	for (int i = 0; i < group; i++)
	{
		int left = p+5*i;
		int right = (p+5*i+4)>r ? r : p+5*i+4;//
		int mid = (left+right)/2;
		bubble(A, &left, &right);
		swap(A, p+i, mid);//
	}

	int pivot = select(A, p, p+(r-p-4)/5, (r-p-4)/10);//找出中位数
	int f  = partition(A, p, r, pivot);
	if(k == f)
		return A[f];
	else if (k <= f - 1)
		return select(A, p ,f-1, k)
	else
		return select(A, p+1, r, k-f);
}


/*
	最接近对点
*/
int closepair(int *A, int low, int high)
{
	int min,i,j,d1,d2,d,mid,p,q;
	if(high-low == 1)
	{
		min = A[high]-A[low];
		return min>0?min:-min;
	}

	m = S中各点的中位数;
	//线性时间选择,找到中位数
	mid = partition(A,low,high,m);
	d1 = divide(A,low,mid);
	d2 = divide(A,mid+1,high);

	for(p = A[low],i = low+1;i<=mid;i++)
	{//找打值最大的
		if(A[i]>p)
			p=A[i];
	}
	for(q = A[high],j = high;j>=mid+1;j--)
	{
		if(A[j]<q)
			q = A[j];
	}

	d = p-q;

	return min(d1,d2,d);
}

int closepair2(S)
{//设S中华的点位平面上的点,它们都有两个坐标值x,y
	m = S中各点x间坐标的中位数;
	通过m构造S1,S2;
	//S1 = {p∈S | x(p)<=m}, S2 = {p∈S|x(p)>m}
	d1 = closepair2(S1);
	d2 = closepair2(S2);
	dm = min(d1,d2);

	P1是S1中x轴上距离分割线l的距离小于dm的所有点的集合;
	P2是S2中距分割线l的距离在dm之内所有点组成的集合;
	将p1和p2中的点根据y轴进行排序;
	设X和Y是排好序的集合;
	对X进行遍历, 每次遍历X时,检查Y中与当前X的点距离在dm之间的所有点(最多6个);
	X从下往上遍历时,检查Y中的区间可在宽为2dm的区间向上移动;
	dl = 为上述扫描方式的最小值;

	return min(dl,dm);
}

/*
	半数集 		    n/2
	half[n] = 1  +    ∑ half[i]
				    i=1
*/
int set(n,int *S)
{
	int i,sum = 1;
	if(s[n] > 0)
		return s[n];
	for(int i = 1; i<=n/2;i++)
	{
		sum = sum+set(i);
	}
	s[n] = sum;
	
	return s[n];
}

/*
	求数组的众数和重数
*/
int number=0;//number表示众数 
int sum=0;//sum表示该众数的重数 
int Partition(int a[],int p,int r)//在a[p]到a[r-1]中随机选择一个元素作为主元
{   int x=a[r-1];
    int i=p-1;
    int temp,j;
    for(j=p;j<=r-2;j++)
    {   if(a[j]<=x)
        {   i++;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    temp=a[i+1];
    a[i+1]=a[r-1];
    a[r-1]=temp;
    return i+1;
}
int Count(int a[],int x,int p,int r)//统计数组中与x相等的元素的个数并返回
{
    int count=0,i;
    for( i=p;i<r;i++)
    {
        if(a[i]==x)
            count++;
    }
    return count;
}
void Modal(int a[],int p,int r)//通过分治法得到数组的众数和该众数的重数
{
    if(p<r)
    {
        int q=Partition(a,p,r);//统计分解法的主元出现的个数
        int temp=Count(a,a[q],p,q+1);//统计分解法的主元出现的个数
        if(sum<temp)
        {
            sum=temp;
            number=a[q];
        }       
        if(q-p-sum>sum)//如果该元素以左的个数大于重数，向左递归
            Modal(a,p,q);   
        else if(r-q-1>sum)//如果该元素以右的个数大于重数，向右递归
            Modal(a,q+1,r);
    }
}

/*
	dynamic
*/

/*
	矩阵连乘,寻找最小划分点
	m[i][j] = 0  i=j
	        = min{m[i][k]+m[k+1][j] + p[i-1]p[k]p[j]}
*/

int matrixChain(int *p, int n, int **m, int **s)
{//n为矩阵的个数,即p.length-1
	int i,j,r,k;

	for (i = 0; i < n; i++)
	{
		m[i][i] = 0;//m[i][i]即 i=j 单一矩阵
	}

	//r为连乘个数
	for (r = 2; r <=n; r++)
	{
		for (i = 0; i <= n-r; i++)//i为连乘矩阵的第一个
		{
			j = i + r - 1;//j为连乘的最后一个
			m[i][j] = maxint;

			for (int k = i; k <= j - 1; k++)
			{//寻找合适的断开点
				int tmp = m[i][k] + m[k+1][j] + p[i]p[k+1]p[j+1];
				if (tmp < m[i][j])
				{
					m[i][j] = tmp;
					s[i][j] = k;
				}
			
			}

		}
	}
	return m[0][n - 1];//返回最小计算个数
}


void trace(int **s,int i, int j,char *a)
{
	if(i==j)
		printf("%s\n", a[i]);
	else
	{
		printf("(");
		trace(s,i,s[i][j],a);
		trace(s,s[i][j]+1,j,a);
		printf(")");
	}
}

/*
	最长公共子序列
	c[i][j] 表示长度为i和长度为j的两个序列的最长公共子序列

	c[i][j] =0     i=0||j=0
	c[i][j] =c[i-1][j-1]+1 i,j>0 x[i]=y[i]
	c[i][j] = max{c[i-1][j],c[i][j-1]}  
*/

void trace(int **b, int i, int j, char *x)
{
	if(i==0||j==0)
		return;
	if(b[i][j] == 1)
		printf("%s\n",x[i]);
		trace(b,i-1,j-1,a);
	else if(b[i][j] = 2)
		trace(b,i-1,j,a);
	else
		trace(b,i,j-1,a);
}

/*
	最长字段和
	f[i]表示包含A[i]的序列
	b[i]来表示a[0]...a[i]的最大子段和，
	b[i]有两种情况
	最大子段一直连续到a[i] 　
	以a[i]为首的新的子段　。
	由此我们可以得到b[i]的状态转移方程：
	b[i]=max{b[i-1]+a[i],a[i]}
*/
int maxarray(int *A, int n)
{//一维
	int pre=0,sum=0;
	for(int i = 0; i<n;i++)
	{
		if(pre>0)
			pre = pre+A[i];
		else
			pre = A[i];

		if(pre > sum)
			sum = pre;
	}

	return sum;
}

int maxmatrix(int **A, int m, int n)
{//m行n列
	int b[n+1],sum = 0;
	for(int i = 1;i < m; i++)
	{
		for(int k = 1;k <=n; k++)
		{
			b[k] = 0;
		}

		for(int j = i;j<=m;j++)
		{
			for(int k = 1;k <= n; k++)
			{
				b[k] = b[k]+a[j][k];
			}
		}

		int max = maxarray(b,n);
		if(max>sum)
			sum = max;

	}

}

int maxarray1(int *a, int left, int right)
{
	int sum = 0;
	if(left == right)
		sum = a[left]>0?a[left]:0;
	else
	{
		int certer = (letf+right)/2;
		int leftsum = maxarray1(a,left,certer);
		int rightsum = maxarray1(a,certer+1,right);

		int s1 = 0;
		int l = 0;
		for(int i = certer;i>=leftl i--)
		{
			l = l + a[i];
			if(l>s1)
				si = l;
		}

		int s2 = 0;
		int r = 0;
		for(int i = center+1; i<= right; i++)
		{
			r = r+a[i];
			if(r > s2)
				s2 = r;
		}

		sum = l+r;
		if(sum < leftsum)
			sum = leftsum;
		if(sum < rightsum)
			sum = rightsum;
	}

	return sum;
}

//最大M字段和
int maxMSum(int m, int n, int *a)
{//b[i][j] j作为最后一项 分为i子段的最大值
	int b[m+1][n+1];

	for(int i = 0; i<=m; i++)
	{
		b[i][0] = 0;
	}
	for(int i = 0; i<=n; i++)
	{
		b[0][i] = 0;
	}

	for(int i = 1; i<=m; i++)
	{
		for(int j = i; j<=i+n-m; j++)
		{
			if(j>i)
			{
				b[i][j] = b[i][j-1]+a[j];

				for(int k = i-1; k<j; k++)
				{
					if(b[i][j] < b[i-1][k]+a[j])
						b[i][j] = b[i-1][k] + a[j];
				}
			}
			else
				b[i][j] = b[i-1][j-1]+a[j];
		}
	}

	int sum = 0;
	for(int i = m; i<=n; i++)
	{
		if(sum < b[m][i])
			sum = b[m][i];
	}

	return sum;
}

/*
	电路布线问题
	a[i][j]为上端接线柱i与下端接线柱j前的最大不相交子集，则：
	若i与j不相连，则i与j前的最大不相交子集等于i与j - 1前或i - 1与j前的最大不相交子集的最大值， 
	即a[i][j] = max(a[i][j - 1], a[i - 1][j])
	若i与j相连，则i与j前的最大不相交子集等于i - 1与j - 1前的最大不想交子集加1， 
	即a[i][j] = a[i - 1][j - 1] + 1
*/

/*	
	背包问题

	01背包
	f[i][j] = max(f[i-1][j], f[i-1][j-Vi] + Wi)

	完全背包
	f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i])
*/

/*
	最长上升子序列

*/
int lis(int *a,int n)
{
	int b[maxint];//b[i]表示以a[i]结尾的最长上升子序列

	for(int i = 0;i<n;i++)
	{
		b[i] = 1;
		for(int j = 0; j<i;j++)
		{
			if(a[j]<a[i] && b[j]+1>b[i])
				b[i] = b[j]+1;
		}
	}
	return max(num);
}

/*
	设字符串A和B的字串A[1...i]和B[1...j]的扩展距离是val(i, j)；
	依题意，字符串A和B有三种可能的情况：
	1）A串最后一个字符是空格，B串最后一个字符是字母，则val(i, j) = val(i-1, j) + k；
	2）A串最后一个字符时字母，B串最后一个字符时空格，则val(i, j) = val(i, j-1) + k；
	3）A串和B串最后一个字符均是字母，则val(i, j) = val(i-1, j-1) + dist(ai , bi)；
	由上可知，val(i, j)具有最优子结构性质，且满足如下递推式：
	val(i, j) = min{ val(i-1, j) + k，val(i, j) + k，val(i-1, j-1) + dist(ai , bi) }
	val(0,0) = 0;
*/


/*
	贪心算法
*/
/*
	这道题的贪心证明，第一步，当只有一个箱子并且小于C时,当前情况满足任何算法，
	所以也满足以最轻的箱子进行贪心选择的性质，
	第二步，假设n个箱子的规模满足用最轻的贪心选择是成立的，
	第三部，对于n+1规模下的箱子(即n+1个箱子),以重量递增序列排序得集合X={x1,x2,x3,x4,x5,,,,xn,xn+1},  
	由第二步得 X1 = {x2,x3,x4,x5,,,,xn,xn+1} 假设总和<=C是x2到xn+1 这个n个规模下得最优解(去掉了x1),
	假设 X2是原问题得最优解,如果按照贪心选择得最优解得  x1∈X2,记包含x1得最优解是S, 
	如果X2不存在x1, 设不存在x1得最优解为X3,因为x1是最轻得,将x1替换掉X3中任意一个箱子肯定也不会超重,
	即n+1问题规模下肯定存在一个包含x1得最优解记为X4,   
	即S和X4下的解都会存在一个x1,再判断S和X4谁是最优解, 
	如果X4是最优解即个数最多 X4-{x1} 的个数应该是大于 S-{x1}的个数,但是S-{1} = X1 所以矛盾了,S才是最优解

*/

/*
	单源最短路径
*/
void Dijkstra(int n, int v, int *dist, int *prev, int **c)//求其他点到点v的最短距离
{/*
	n是顶点个数，
	v是源，
	dist数组存其他点到v的距离，
	prev该点的上一个点，
	c[i][j]存两个点i、j权值，如果两个点是没有边连接的话存的值是一个远大于问题规模的数
	s[] 为标记数组
*/
	int s[maxint];//maxint为远大于规模的数
	for (int i = 1; i <= n; i++)
	{//赋初值
		dist[i] = c[v][i];
		s[i] = false;

		if (dist[i] == maxint)
			prev[i] = 0;
		else
			prev[i] = v;
	}

	dist[v] = 0; s[v] = true;

	for (int i = 1; i < n; i++)//需要进行n-1次,源点v不需要进行
	{
		int temp = maxint;
		int u = v;

		for (int j = 1; j <= n; j++)
		{
			if ( (!s[j]) && (dist[j] < temp ) )
			{
				u = j;
				temp = dist[j];
			}
		}//找到没有走过的路径的最小的并且与源点最短的点

		s[u] = true;//设为走过

		for (int j = 1; j <= n; j++)
		{//设置最新的路径，保存上一个点
			if ( (!s[j]) && (c[u][j] < maxint) )
			{//没有走过的与u(即当前走到的结点)相连的点
				int newdist = dist[u] + c[u][j];
				if (newdist < dist[j])
				{
					dist[j] = newdist;
					prev[j] = u;
				}
			}
		}
	}//for

}


/*
	最小生成树
*/
void prim(int n, int **c)
{//n是问题规模，c[i][j]是表示i点和j点的权值
	int lowcost[maxint];
	int closest[maxint];
	bool s[maxint];

	s[1] = true;

	for (int i = 2; i <= n; i++)
	{
		lowcost[i] = c[1][i];
		closest[i] = 1;
		//closest[i] 表示属于V-S 的 i点，和属于S中的点与i点最近的点，初始化为1；  lowcost[i]就是c[i][closest[i]] 与i不再同一集合的最小的权值

		s[i] = false;
	}

	for (int i = 1; i < n; i++)
	{
		int min = inf;//无限大 infinite
		int j = 1;

		for (int k = 2; k <= n; k++)//k不在S中并且是k是邻边,循环找出最小的邻边
		{
			if ( (lowcost[k] < min) && (!s[k]))
			{
				min = lowcost[k];
				j = k;
			}
		}

		s[j] = true;

		for (int k = 2; k <= n; k++)
		{//找出V-S中的点与j点相邻并且小于与原来S中某一个点的最小值，就向最接近的值和点改变新加进的j
			if ( (c[j][k] < lowcost[k]) && (!s[k]) )
			{
				lowcost[k] = c[j][k];
				closest[k] = j;
			}
		}
	}
}


/*
	回溯
*/
#include<stdio.h>

int **M;//各作业所需的处理时间
int *x;//当前作业调度
int *bestx;//当前最优作业调度
int *f2;//机器二完成处理的时间
int f1;//机器一完成处理的时间
int f;//完成时间和
int bestf;//当前最优值
int n;//作业数

void Perm(int *A, int f, int l)
{//f是数组的第一个位置初始0, l最后一个位置即 长度 - 1

	if (f == l)
	{//递归的边界条件 即n = 1
		for (int i = 0; i <= l; i++)
		{
			printf("%d", A[i]);//打印一个排列
		}

		printf("\n");
	}
	else
	{	
		//Perm(list, f+1, l);

		for (int i = f; i <= l; i++)
		{
			if (f != i)
				swap1(&A[f],&A[i]);

			Perm(A, f+1, l);

			if (f != i)
				swap1(&A[i],&A[f]);			
		}
	}
}


void DJDD_Backtrack(int i)
{
	if(i>n)
	{//到达叶子结点
		for(int j=1; j<=n; ++j)
			bestx[j]=x[j];
		bestf = f;
	}else
		for(int j=i; j<=n; ++j)  // 因为问题的解空间是一颗由x[1:n]的所有排列构成的排列树
		{ // 所以第i次所调度的作业是从序号为i到n的作业中选择一个座位子树分支
			f1 += M[x[j]][1]; // +第i次所调度的作业在机器1上的处理时间
			f2[i] = ((f2[i-1]>f1) ? f2[i-1] : f1) + M[x[j]][2];
			f += f2[i];      //  +第i次所调度的作业在机器2上的处理时间
			if(f<bestf)
			{
				Swap(x[i], x[j]);
				Backtrack(i+1);
				Swap(x[i], x[j]);
			}
			f1 -= M[x[j]][1]; // -第i次所调度的作业在机器1上的处理时间
			f -= f2[i];       // -第i次所调度的作业在机器2上的处理时间
		}
		
}


int n;//集装箱数量
int *x;//当前解, 标记数组 1为选择放入 0为没选择
int *bestx;//当前最优解
int *w; //集装箱重量数组
int c; //第一艘轮船的载重量
int cw;//当前载重量
int bestw;//当前最优载重量
int r;//剩余集装箱重量

void Backtrack(int i)
{//i,搜索第i层结点,初值为1
	if(i>n)
	{//到达叶子节点
		if(cw > bestw)//当前载重量大于当前最优载重量
		{
			for(int j = 1; j<=n; j++)
			{
				bestx[j] = x[j];
				bestw = cw;
				return;
			}
		}
	}

	r -= w[i];//

	if(cw + w[i] <= c)
	{//当前载重加上备选放入的箱子小于轮船的载重量
	 //搜索左子树

	 x[i] = 1;
	 cw += w[i];
	 Backtrack(i+1);
	 cw -= w[i];
	}
	if(cw + r > bestw)
	{//当前的重量加上剩余的集装箱重量大于当前最优解
	 //遍历右子树

	 x[i] = 0;
	 Backtrack(i+1);
	}

	r += w[i];//
}